/**
  (C) 2005 - Boston University
  		Adam D. Bradley and Michael Ocean
  Contact: Michael Ocean 

  This work is a part of the larger snBench project.  Information
  can be found at: http://csr.bu.edu/snbench 
  
  This program is free software; you can redistribute it and/or
  modify it under the terms of Version 2 of the GNU General Public 
  License.
  
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.
  
  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free
  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
**/

package step;

import java.io.OutputStream;
import java.net.URI;
import java.net.URISyntaxException;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Map;
import java.util.NoSuchElementException;
import step.exceptions.STEPException;
import sxe.SxeMonitor;
import snbenchlib.Log;
import snbenchlib.Trace;
import snbenchlib.Util;
import snbenchlib.XML;
import snobject.snObject;
import snobject.snCommand;
import snobject.InvalidCommand;
import snobject.UnknownCommand;

public abstract class Node
{
	private static final int FUTURE_UNIT = Calendar.MINUTE;
	private static final int FUTURE_TIME = 5;
 
    /* ------------------------------------------------------------------ */
    /* More-or-less stable properties */
    protected String ID;
    protected String SourceGraphID;
    protected String bindTo;
    protected String bindingSuggested;

    /* flowtype for this node */
    protected Map<String,FlowType> types;
    protected Node[] children;
    protected String[] childalias;
    protected Node[] parents;

    /* path to this data on the web when hosted */
	protected java.net.URI uriWebPathToResource;

	/* value is a run-time property for non ValueNodes */
    protected snObject value;
    
    private int cost;

    /* ------------------------------------------------------------------ */
    /* Dynamic runtime properties */
    private snObject[] rt_inputs;
    private boolean[] rt_freshInputs;
    protected boolean rt_evaluated;
    protected boolean rt_garbage;
    private int rt_garbage_ttl;
    protected Calendar rt_persistUntil;
    protected boolean rt_wanted;
	
    /* ------------------------------------------------------------------ */
    /* Debug and statistics properties */

    private int rt_evaluationCount = 0;
    private snObject rt_prevValues[];
	private java.net.URI sxeUri;
	
	/**
	 * ID should not be null.  If null is passed in, no error will
	 * occur.  Expect graph operations to fail if null id'ed nodes
	 * are present.
	 * 
	 * @param id - the id of this node.  Should be unique w.r.t. the
	 * other nodes in the step graph.
	 */
	public Node(String id) {
		ID = id;
		   
		children = new Node[0];
		// used to maintain old splice node names
		childalias = new String[0];
		
		types = new HashMap<String,FlowType>();
		parents = new Node[0];
		rt_prevValues = new snObject[5];
		rt_inputs = new snObject[0];
		rt_freshInputs = new boolean[0];
		value = null;
		rt_wanted = false;
		rt_garbage = false;
		rt_garbage_ttl = 0;
		cost = 1;
		bindTo = null;
		bindingSuggested = null;
    }

	/**
	 * constructs a node with no ID. It's recommended
	 * that an ID is provided before any actual use of
	 * this node (eg, it is added to a graph)
	 */
    public Node() {
    	ID = null;
    	
		children = new Node[0];
		childalias = new String[0];
		types = new HashMap<String,FlowType>();
		parents = new Node[0];
		rt_prevValues = new snObject[5];
		rt_inputs = new snObject[0];
		rt_freshInputs = new boolean[0];
		value = null;
		rt_wanted = false;
		rt_garbage = false;
		rt_garbage_ttl = 0;
		cost = 1;
		bindTo = null;
		bindingSuggested = null;
    }

    public abstract Node ShallowCopy();
    
    protected static void CopyNonRTPropertiesFromAtoB(Node A, Node B){
    	B.ID = A.ID;
    	B.value = A.value;
    	B.bindingSuggested = A.bindingSuggested;
    	B.bindTo = A.bindTo;
    	B.SourceGraphID = A.SourceGraphID;
    	B.cost = A.cost;
    }
    
    /**
     * increase the number of children this node 
     * has to the value 'n' -- does nothing if 'n'
     * is smaller than the number of children.
     * 
     * This leaves the children array in a bad
     * state so be sure to actually add those 
     * children before doing anything else!
     * 
     * The new child (children) slots are the 
     * last children in the sequence.
     *  
     * @param n
     */
    private void GrowChildren(int n) {
		assert(n >= children.length);
		Node newchildren[] = new Node[n];
		System.arraycopy(children, 0, newchildren, 0, children.length);
		children = newchildren;
	
		String newchildalias[] = new String[n];
		System.arraycopy(childalias, 0, newchildalias ,0, childalias.length);
		childalias = newchildalias;
		
		snObject newinputs[] = new snObject[n];
		System.arraycopy(rt_inputs, 0, newinputs, 0, rt_inputs.length);
		rt_inputs = newinputs;
	
		boolean newFreshInputs[] = new boolean[n];
		System.arraycopy(rt_freshInputs, 0, newFreshInputs, 0, rt_freshInputs.length);
		rt_freshInputs = newFreshInputs;
    }

    /** 
     * Like GrowChildren, but for parents -- adds a slot to the
     * parent array.
     * 
     * @param n
     */
	private void GrowParents(int n) {
		assert(n >= parents.length);
		Node newparents[] = new Node[n];
		System.arraycopy(parents, 0, newparents, 0, parents.length);
		parents = newparents;
	}

	/**
	 * Set's the ID of the node to the specified string.  Does not
	 * check if the ID is used elsewhere (because this is a NODE method
	 * not a GRAPH method) -- be sure to check the uniqueness of the
	 * ID before adding to the graph.
	 * 
	 * @param newid
	 */
	public void setID(String newid)
	{
		this.ID = newid;
	}
    
	/**
	 * The order of elements in the "parents" array has no semantic meaning,
	 * while the order of children is very important.  As such, we
	 * "encourage" programmers to use the AddChild interface, which invokes
	 * this one implicitly.
	 *
	 * This is an idempotent operation, which makes the result delivery 
	 * algorithms a lot simpler (and faster).  However, it also means you 
	 * need to be careful to only remove a "parent" link when ALL of the 
	 * reciprocal "children" links have been removed.
	 *
	 */
	protected void AddParent(step.Node n) {
		AddParentRef(n);
	}

	/**
	 * Add a reference to the parent[] array.
	 * Only use it if you REALLY know what you're doing
	 * as it does not ensure that children are reciprocally
	 * added, etc.
	 */
	private void AddParentRef(step.Node n) {
		int i;
		
		for (i=0 ; i<parents.length ; i++) {
		    if (parents[i] == n) {
				return;
		    }
		}
		int idx = parents.length;
		GrowParents(idx + 1);
		parents[idx] = n;
	}

	
	/**
	 * Remove any references to n in this.parents[].
	 * 
	 * A deleted node should do this to all of it's
	 * children.
	 * 
	 * Only use it if you REALLY know what you're doing
	 * as it does not take care of the opposite direction's
	 * linking (this no longer has the parent, but the
	 * parent may still point to this as a child)
	 */
	public void RemoveParentRef(step.Node n) {
		if(parents == null)
			return;
		
		for (int i=0 ; i<parents.length ; i++) {
		    if (parents[i] == n) {
				// remove 
		    	ShrinkParents(i);
		    }
		}
	}

	/**
	 * Remove any references to the node n in 
	 * 	this.children[] -- includes removal of
	 * 	input/freshinput as well
	 * 
	 * A deleted node should do this to all of it's
	 * parents.
	 * 
	 * Only use it if you REALLY know what you're doing.
	 * As above, bi-directionality of operation is NOT
	 * handled.
	 */
	public void RemoveChildrenRef(step.Node n) {
		if(children == null)
			return;
		
		for (int i=0 ; i<children.length ; i++) {
		    if (children[i] == n) {
				// remove 
		    	ShrinkChildren(i);
		    }
		}
	}
	

	/**
	 * Shrinks the parents array "around" a node
	 * i.e.,
	 *  parents = parents[0..i-1] + parents[i+1..n] 
	 *
	 *  Be careful! doesn't clean up this ousted
	 *  node's references to this, just removes this's 
	 *  reference to the node
	 */
	private void ShrinkParents(int i) {
		assert(i >= 0);
		
		// clear out the reference so the Java GC will reap
		parents[i]=null;
		
		if(parents.length == 1) 
		{			
			parents = new Node[0];
			return;
		}
		
		Node newnodes[] = new Node[parents.length - 1];
		System.arraycopy(parents, 0, newnodes, 0, i);
		System.arraycopy(parents, i+1, newnodes, i, newnodes.length - i);
		parents = newnodes;
	}

	/**
	 * Shrinks the children array "around" a node
	 * i.e.,
	 *  children = children[0..i-1] + children[i+1..n] 
	 *  freshinputs = freshinputs[0..i-1] + freshinputs[i+1..n]
	 *  input = input[0..i-1] + input[i+1..n]
	 *  
	 *  Be careful! doesn't clean up this ousted
	 *  node's references to this, just removes this's 
	 *  reference to the node
	 */
	private void ShrinkChildren(int i) {
		assert(i >= 0);

		// clear out the referenceS so the Java GC will reap
		children[i]=null;
		rt_inputs[i]=null;
		
		if(children.length == 1) 
		{
			children = new Node[0];
			rt_inputs = new snObject[0];
			rt_freshInputs = new boolean[0];
			
			return;
		}
		
		//remove the index from children,inputs and fresh inputs
		
		Node newnodes[] = new Node[children.length - 1];
		System.arraycopy(children, 0, newnodes, 0, i);
		System.arraycopy(children, i+1, newnodes, i, newnodes.length - i);
		children = newnodes;
		
		snObject newinputs[] = new snObject[rt_inputs.length - 1];
		System.arraycopy(rt_inputs, 0, newinputs, 0, i);
		System.arraycopy(rt_inputs, i+1, newinputs, i, newinputs.length - i);
		rt_inputs = newinputs;

		String newalias[] = new String[childalias.length - 1];
		System.arraycopy(childalias, 0, newalias, 0, i);
		System.arraycopy(childalias, i+1, newalias, i, newalias.length - i);
		childalias = newalias;
		
		boolean newfreshinputs[] = new boolean[rt_freshInputs.length - 1];
		System.arraycopy(rt_freshInputs, 0, newfreshinputs, 0, i);
		System.arraycopy(rt_freshInputs, i+1, newfreshinputs, i, newfreshinputs.length - i);
		rt_freshInputs = newfreshinputs;
	}
	
	/**
	 * Add a child (parameter) node.  
	 * Implicitly adds the "parent" back-link to n.
	 * 
	 * (remember that children added are not added as far as the
	 *  graph is concerned, so be sure to also add the node the the graph)
	 */
	public void AddChild(step.Node n) {
		AddChildRef(n);
		n.AddParent(this);
	}

	/**
	 * adds the child node to the end of the children array.  Doesn't
	 * take care of any reciprocal linking so use extreme caution when
	 * using this method.
	 * 
	 * @param n
	 */
	private void AddChildRef(step.Node n) {
		int idx = children.length;
		GrowChildren(idx+1);
		children[idx] = n;
	}

	/**
	 * Adds a flow type to the map of flowtype data for this node.
	 * @param ft
	 */ 
	public void AddFlowType(FlowType ft) {
		types.put(ft.getLabel(),ft);
	}
	
	/**
	 * Update "this" node's parent links such that if they have
	 * children that point to a node with the same ID as that of
	 * nTarget, that they will point to this new node (nTarget)
	 *
	 * @param nTarget
	 * 
	 */
	public void graft_RedirectParentsToNode(step.Node nTarget) {
				
		for (int i=0 ; i<parents.length ; i++) {
			Node nTmp = parents[i];
			for(int j=0;j<nTmp.children.length;j++){
				if(nTmp.children[j] == this) {
					nTmp.children[j]=nTarget;
					nTmp.childalias[j] = new String(GetID());
				}
			}
		}
	}
	
	/**
	 * Update "this" node's children links such that if they have
	 * parents that point to this node, that they will point to 
	 * this new node (nTarget)
	 *  
	 * @param nTarget
	 */
	public void graft_RedirectChildrenToNode(step.Node nTarget){
		
		Node nTmp = null;
		for (int i=0 ; i<children.length ; i++) {
			nTmp = children[i];
			for(int j=0;j<nTmp.parents.length;j++){
				if (nTmp.parents[j] == this) {
					nTmp.parents[j]=nTarget;
				}
			}
		}
	}
	
	/**
	 * Same method as Realize; ensure all nodes reachable
	 * from this node (this and descendants) have been 
	 * added to the graph specified.  ALSO ensures that opcode
	 * nodes are valid opcodes, let terms/triggers point to
	 * valid nodes, etc.
	 *  
	 * @param g
	 * @return
	 */
	public final boolean GraphAttach(step.Graph g){
		return Realize(g);
	}
	
	/**
	 * Same method as Realize; ensure all nodes reachable
	 * from this node (this and descendants) have been 
	 * added to the graph specified.  ALSO ensures that opcode
	 * nodes are valid opcodes, let terms/triggers point to
	 * valid nodes, etc.
	 * 
	 * Only called by graft
	 */
	public final boolean Realize(step.Graph g) {
		try {
			g.AddNode(this);
		} catch (DuplicateID e) {
			// This is a realization failure --
			// the node could not be added because
			// a different node with the same ID
			// exists in the graph.
			Log.graph.printStackTrace(e);
			return false;
		}
		
		String theURI = "/snbench/sxe/node/" + ID + "/";
		uriWebPathToResource = URI.create(theURI);
		
		for (int i=0 ; i<children.length ; i++) {
			if(!children[i].Realize(g))
				return false;
		}
		return true;
	}

	/*************************************
	 * A single STEP will be assigned across
	 * (potentially) many SXEs.  This single STEP must be divided into several
	 * smaller STEP graphs, each sent to the appropriate SXE.  Assuming
	 * at this point all nodes are tagged with appropriate BindTo strings,
	 * which are the URIs of the SXEs on which they will be deployed, seperate
	 * graphs must be generated for each from a traversal.
	 * 
	 * Also, where these splits across SXEs occur, sender/reciever nodes must be
	 * placed to facilitate the eventual product of a single STEP graph.
	 * ***********************************/
	private Hashtable<String, Graph> ht;

	private final Graph getGraph(String sSXE){
		if(ht==null)
			ht = new Hashtable<String, Graph>();
		Graph g = (Graph)ht.get(sSXE);
		if(g!=null)
			return g;
		else{
			g = Graph.newEmptyGraph(sSXE);
			ht.put(sSXE,g);
			return g;
		}	
	}
	
	/*
	public final void Splitter(Graph g, String sSXE) throws URISyntaxException{
		// back up children and parents 
		Node nChildren[] = new Node[this.children.length];
		System.arraycopy(children, 0, nChildren, 0, children.length);
		this.children = new Node[0];
		Node nParents[] = new Node[this.parents.length];
		System.arraycopy(parents, 0, nParents, 0, parents.length);
		this.parents = new Node[0];
		
		if(sSXE.equals(this.bindTo)||(this.bindTo==null)){	
			g.AddNode(this);
			for(int i=0;i<nChildren.length;i++){
				this.AddChild(nChildren[i]);
				children[i].Splitter(g,sSXE);
			}		
		}
		else{
			// new graph for next id
			ReceiverUdpSocketNode rsn = new ReceiverUdpSocketNode(this.ID,new URI(this.bindTo));
			g.AddNode(rsn);
			
			Graph g2 = getGraph(sSXE);
			SenderUdpSocketNode susn = new SenderUdpSocketNode(rsn.ID,new URI(rsn.getBindTo()));
			g2.AddNode(susn);
			susn.AddChild(this);
			g2.AddNode(this);
			for(int i=0;i<children.length;i++){
				children[i].Splitter(g2,sSXE);			
			}
		}
	}
	*/
	/************************************************************************/
	
	/**
	 * This gets overridden by LastTriggerEval to
	 * implement non-tree linking in the graph.  
	 * This method is part and parcel with Realize, ensuring
	 * that the move from node (alone) to graph (inter-linked)
	 * is 'normal'
	 * 
	 * SpliceNode used to override it, but it was ugly.
	 * step.Graph.ResolveSplices() should handle all of that now.
	 * 
	 * This is usually invoked by step.graph.Normalize().
	 */
	protected step.Node Normalize(step.Graph g) throws DanglingSplice {
		for (int iter=0 ; iter<children.length ; iter++) {
			children[iter].Normalize(g);
		}
		return this;
	}

	/**
	 * This should be called to let the node that it should prepare itself
	 * to be evaluated, i.e., it's not just a representation but an 
	 * "instruction" in a running system.  This is the cue for function 
	 * calls to bind to FunctionWrappers, network-aware nodes to bind to
	 * HTTP access points, sensors to open their devices, etc.
	 * Note that this call should not recurse; it is a local operation.
	 * 
	 * This is usually invoked by step.graph.Bind()
	 */
	protected void Bind() throws ClassNotFoundException {
	}
	
    /**
     * We need a way to delay the evaluation of a trigger's right-children
     * which are not left-children, the branches of conditional nodes, etc.  
     * 
     * This is done with the "wanted" flag.
     */
    protected void SetWanted(boolean v) throws EvaluationFailure { 
	    /* override to block/alter propogation */
	    rt_wanted = v;
	    for (int i=0 ; i<children.length ; i++) {
		    children[i].SetWanted(v);
	    }
    }
    
    /**
     * @return - state 'wanted', set by parents when in evaluation
     */
    protected boolean IsWanted() { return rt_wanted; }

   /**
    * @return the node's ID.  Be warry of nodes w/ ID = null!
    */
    public final String GetID() { 
    	return ID;
    }
    
    /**
     * RunTime property: Sets this node as garbage and indicates the
     * time at which we'd like the node to be 
     * removed from the system.  (Often "now")
     * @param rt_persistUntil 
     */
	public void markAsGarbage() {
		rt_garbage = true;
		Calendar c = Calendar.getInstance();
		c.add(FUTURE_UNIT,FUTURE_TIME);
		this.rt_persistUntil = c;
		Log.janitor.log("Node '" + ID + "' marked for deletion." +
				" Will expire in " + FUTURE_TIME + " Minute(s).",
				Trace.MINIMAL);
	}
    
	public boolean isGarbage(){ return rt_garbage; }
	
	/**
	 * @return run-time property persist until is past.  Doesn't check
	 * the garbage field
	 */
	public boolean checkExpired() {
		if(rt_persistUntil!=null)
			return rt_persistUntil.before(Calendar.getInstance());
		else
			return false;
	}

    /* ------------------------------------------------------------------ */
    /* Intra-STEP Interface */

    /**
     * Some nodes (e.g. sockets, triggers) may want to override this to
     * provide their own semantics.
     */
	public boolean IsEnabled() {
		if (rt_evaluated || !rt_wanted)
			return false;
		if(rt_garbage)
			return false;
		
		return HasFreshInputs();
	}

	/** 
	 * Calls node's Evaluate() and (if the node is no longer needed)
	 *  if so calls sxeMonitor.ReportEvalComplete and await further instruction from the SSD
	 *  
	 * Caller must ensure node.IsEnabled before calling otherwise behavior is unknown.
	 * 
	 * @throws EvaluationFailure
	 */
	public final void DoEvaluate() throws EvaluationFailure
    {
		Evaluate();
		if(value!=null)
			Log.evaluator.log(
					"Evaluated: "+ this.ID + "\t\tResult=" + this.value.toString(),
					Trace.VERBOSE);
		else{
			Log.evaluator.log(
					"Evaluated: "+ this.ID + "\t\tResult=null",
					Trace.VERBOSE);
		}
				
		// check if complete, if so tell the SSD we're done.
		// this is where we should:
		// 
		// 1) see if we are a (root node && have exectued && !socketNode)
		//    [note, triggers never changed their evaluated state]
		// 2) tell the SSD that this tree is complete
		// 3) further instruction will come from the SSD,
		// 
		// NOTE) We could delete this program because it cannot be in use by other
		//  programs without our knowledge as there would be a splice or a socket at
		//  the head.  Instead, though we don't reclaim resources/delete locally because
		//  we want to keep the SSD in the role of power.
		//
		if(this.IsOrphan() && (this.rt_evaluated) && (!(this instanceof SocketNode)||!(this instanceof AbstractTrigger))){		
			Log.evaluator.log(
					"Determined program : "+ this.getGraphID() + " is no longer in use (not Enabled).  Informing SSD",
					Trace.MINIMAL);

			
			SxeMonitor.reportEvaluationComplete(this.getGraphID());

			/* below is how we would reclaim resources here -- we don't though
			ArrayList<Node> al = new ArrayList<Node>();
			al.add(this);
			while(!al.isEmpty()){
				Node n = al.remove(0);
				n.markAsGarbage();
				SxeMonitor.incrAvailableResources(Graph.ComputeNeeds(n));
				
				if(!(n instanceof LastTriggerEval)){
					for(int i=0;i<n.children.length;i++){
						al.add(n.children[i]);
					}
				}
			}
			*/
		}

    }

    
    /**
	 * Push fresh result to parent nodes
	 */
	public final void PushResult() {
		for (int i=0 ; i<parents.length ; i++) {
			parents[i].PushFreshInput(value, this);
		}
		rt_evaluationCount++;
	}
	
	public final snObject GetValue() {
		return value;
	}


	/**
	 * 	An Orphan has no logical parents, which is equiv. to being a logical root
	 * (or logical local root in the case of subgraphs).  
	 * 
	 * logical insofar as we intentionally ignore the 'soft'-links created
	 * by LTE's, so a trigger with an LTE pointing to it WILL be an Orpah
	 * according to this method 
	 * 
	 * @return true if (|parents| == 0) or parents are LTE links
	 */
	public final boolean IsOrphan() {
		Node p = null;
		
		if(parents == null){
			System.err.println("Node " + GetID() + " has parents == null.");
		}
		
		if (parents.length == 0) { 
			return true;
		}
    	else if(this instanceof AbstractTrigger)
   		{
			boolean ok = true;
			for(int j=0;j<parents.length;j++){
				p = parents[j];
				if(!(p instanceof LastTriggerEval)){
					ok=false;
				}
			}
			if(ok){
				return true;
			}
   		}

    	return false;
    }

	/** 
	 * Returns whether this node has children to recurse into or not.
	 * Over-ridden by LastTriggerEval to ensure we ignore the
	 * soft-links they create.
	 * 
	 * @return
	 */
	public boolean IsLeaf() {
		return (children.length == 0);
	}

    /**
     * This is the method to override to implement the semantics of a node.
     */
    protected abstract void Evaluate() throws EvaluationFailure;

    /**
     * Some nodes (Triggers, Consts, LTEs) need to override this method to
     * block the "clear" from propogating. 
     */
    protected void ClearEvaluatedFlags() throws EvaluationFailure
    { 
    	/* DOME : each "clear" should have a 2-part ID,
    	 sender-ID and serial number.  We should reject
    	 repeated attempts to clear from the same
    	 id:serial pair.  This will fix the nasty
    	 problem with letonce instances inside of 
    	 persistent triggers. */
    	rt_evaluated = false;
    	for (int i=0 ; i<children.length ; i++) {
    		children[i].ClearEvaluatedFlags();
    	}
    }

    /**
     * check if a node w/ ID specified is a child of this
     * 
     * @param ID
     * @return
     */
    public boolean hasChild(String ID){
    	return(Util.findInArray(ID, this.children) >= 0);
    }

    /**
     * check if a node w/ ID specified is a parent of this
     * 
     * @param ID
     * @return
     */
    public boolean hasParent(String ID){
    	return(Util.findInArray(ID, this.parents) >= 0);
    }

    /**
     * Disconnect it's node from both its parents and children,
     * striking their references to this node and deleting all
     * instances of it.
     *
     */
    protected void cleanup(){
    	/* remove any references to this node from our children */
    	for(int i=0;i<children.length;i++){
    		children[i].RemoveParentRef(this);
    	}
    	
    	/* remove any references to this node from our parents */
    	for(int i=0;i<parents.length;i++){
    		parents[i].RemoveChildrenRef(this);
    	}
    
    	/* clear out any values, extra hanging references, etc */
    	//FIXME: put me back
		parents = null;
		children = null;
		childalias = null;
		value = null;
		rt_freshInputs = new boolean[0];
		rt_inputs = null;	
    }
    

    /**
     * Run time method that sets this.freshInput[n] = false
     * @param n
     */
    protected final void ClearFreshInput(int n) {
    	rt_freshInputs[n] = false;
    }

    /**
     * Run time method that sets this.freshInput[*] = false
     */
    protected final void ClearFreshInputs() {
    	for (int i=0 ; i<rt_freshInputs.length ; i++) {
    		ClearFreshInput(i);
    	}
    }

    
    /**
     * @return true if all this.freshInput[*] = true
     */
    protected final boolean HasFreshInputs() {
    	for (int i=0 ; i< rt_freshInputs.length ; i++) {
			if (!rt_freshInputs[i]){
				return false;
			}
		}
    	return true;
    }

    /**
     * @return true if this.freshInput[n] = true
     * @param n
     */
    protected final boolean HasFreshInput(int n) {
    	assert((n >= 0) && (n < rt_inputs.length));
    	return rt_freshInputs[n];
    }

    /**
     * Run time method to retrieve cached value passed from child n
     * sets fresh input on this value to false 
     * (indicating that it has been read)
     * 
     * @param n - get value corresponding to child number n
     */
    protected final snObject GetInput(int n) {
    	assert((n >= 0) && (n < rt_inputs.length));
    	rt_freshInputs[n] = false;
    	return rt_inputs[n];
    }

    /**
     * RunTime method: Set the value of this node to @param nv
     * does NOT pass values up the parents
     * does NOT set fresh input for parents, etc.
     * does cache previous values 
     */
    protected final void SetValue(snObject nv) {
    	if (rt_prevValues!=null) {
    		if (rt_prevValues.length>1)
    			for (int i=rt_prevValues.length-1 ; i>0 ; i--) {
    				rt_prevValues[i] = rt_prevValues[i-1];
    			}
    		rt_prevValues[0] = value;
    	}
    	value = nv;
    }
    
    /**
     * Sets the value of this node to the passed argument and
     * NOTHING else.  No coherence up the graph, no caching, nothing.
     * @param nv
     */
    public void SetValueForGUI(snObject nv) {
    	value = nv;
    }
        
    /**
     * Push the fresh input flag to the immediate parents of this to
     * change any child that points to 'who' to reflect 'who's new value
     * and freshness of value
     * 
     * may be overridden by subclasses that maintain a buffer
     * (specifically triggerreadnodes that are buffered)
     * 
     * @param value - the new value of the node 'who'
     * @param who - the node who's reporting the new value
     */
    protected void PushFreshInput(snObject value, step.Node who)
    {
    	for (int i=0 ; i<children.length ; i++) {
    		/**
    		 * Note - we have to iterate over the whole children array,
    		 * even if we find a first match, because one child may be
    		 * grafted onto several points (CSE of multiple arguments) 
    		 */
    		if (children[i] == who) {
    			rt_inputs[i] = value;
    			rt_freshInputs[i] = true;
				// SJJ - SMOD: 
    			// If this node becomes enabled, move it to the runnable queue 
				//System.out.println("PushFreshInput: node="+GetID()+" evaluated="+evaluated+" wanted="+wanted+" IsEnabled="+IsEnabled());
    			//SchedulerFactory.getScheduler().scheduleIfWaiting(this);
    		}
    	}
    }

    /* ------------------------------------------------------------------ */
    /* Debug and statistics interface */

    public final int EvaluationCount() { return rt_evaluationCount; }
    public final snObject PrevValue(int n) 
    { 
	return ((rt_prevValues!=null) && (n<rt_prevValues.length))?rt_prevValues[n]:null; 
    }


	/* ---------------------------------------------------------------- */
	/* Web exposed interfaces                                           */

	protected void ReceiveClear(snCommand c) 
	throws InvalidCommand, EvaluationFailure {
		throw new InvalidCommand(this, c);
	};
	
	protected void ReceiveWant(snCommand c) 
	throws InvalidCommand, EvaluationFailure { 
		throw new InvalidCommand(this, c); 
	};

	protected void ReceiveDontWant(snCommand c) 
	throws InvalidCommand, EvaluationFailure {
		throw new InvalidCommand(this, c);
	};

	public final void ReceiveCommand(snCommand c) 
	throws InvalidCommand, UnknownCommand, EvaluationFailure {
		if (c.equals(snCommand.CLEAR)) {
			ReceiveClear(c);
		} else if (c.equals(snCommand.WANT)) {
			ReceiveWant(c);
		} else if (c.equals(snCommand.DONTWANT)) {
			ReceiveDontWant(c);
		} else {
			throw new UnknownCommand(this, c);
		}
	};

	/**
	 * @return an XML formatted string <tagName id= href=uri">
	 * without value, etc.  Just a link to the resource
	 */
	public String GetLinkXML() {
		return "<" + TagName() + " " + 
			"xmlns=\"" + XML.XMLNS + "\" " +
			"id=\"" + ID + "\" href=\"" + uriWebPathToResource + "\" />";
	}

	/**
	 * @return an XML formatted string <tagName id= href=uri">
	 * with value, type, run-time inspection properties, etc.
	 */
	public String GetInfoXML() {
		return GetInfoXML("");
	}

	/**
	 * extraXML is inserted as a child of the node
	 * @return an XML formatted string <tagName id= href=uri">
	 * with value, type, run-time inspection properties, etc.
	 */
	public String GetInfoXML(String extraXML) {
		String b = 
			"<" + TagName() + " " + 
			"xmlns=\"" + XML.XMLNS + "\" " + 
			"id=\"" + GetID() + "\">\n";
		if (extraXML != null)
			b += "  " + extraXML + "\n";
		if (value != null)
			b += "  <type>" + value.getXmlMimeType() + "</type>\n";
		b += "  <source>" + SourceGraphID + "</source>\n";
		b += "  <operands>\n";
		for (int i=0 ; i<children.length ; i++) {
			b += "    <" + children[i].TagName() + 
				" id=\"" + children[i].GetID() + 
				"\" href=\"/snbench/sxe/node/" + 
				children[i].GetID() + "\"" + 
				" fresh=\"" + 
				(HasFreshInput(i)?"true":"false") + "\"" + 
				"/>\n";
		}
		b += 
			"  </operands>\n" + 
			"  <operandof>\n";
		for (int i=0 ; i<parents.length ; i++) {
			b+= "    <" + parents[i].TagName() + 
				" id=\"" + parents[i].GetID() + 
				"\" href=\"/snbench/sxe/node/" + 
				parents[i].GetID() + "\"/>\n";
		}
		b += 
			"  </operandof>\n" +
			("  <value href=\"/snbench/sxe/node/" + GetID() + 
			 "/data\"/>\n") +
			(IsWanted()?"  <wanted/>\n":"") + 
			(IsEnabled()?"  <enabled/>\n":"") +
			(rt_evaluated?"  <evaluated/>\n":"") +
			(isGarbage()?"  <garbage>" + rt_garbage_ttl + "</garbage>\n":"") +
			("  <evaluationcount value=\"" + 
			 (new Integer(EvaluationCount())).toString() + 
			 "\"/>\n") + 
			"</" + TagName() + ">\n";
		return b;
	}

    /* ------------------------------------------------------------------ */
    /* Serializer                                                         */
    /* For use by compilers with STEP targets and SDs which need to send  */
    /* partial graphs to SXEs.                                            */

    public abstract String TagName();
   
    /**
     * serialize the node and all descendants to the provided stream,
     * tabbed in depth amount.  Handles resolved splices such that
     * the output should show splice nodes (and nodes should not
     * have multiple parents).
     * 
     * @param out
     * @param depth
     * @param attrs
     * @throws java.io.IOException
     */
    public void WriteBasis(OutputStream out, int depth, String attrs) throws java.io.IOException
    {
    	Indent(out, depth);
    	    	
    	out.write(("<" + TagName() + " id=\"" + ID + "\"").getBytes());
    	if(!getBindTo().equals(""))
    		out.write((" bindTo=\"" + getBindTo() + "\"").getBytes());
    	
    	if ((attrs!=null) && (attrs.length()>0)) {
    		out.write((" " + attrs).getBytes());
    	}
    	if ((types.size() > 0) || (children.length > 0)) {
    		out.write(">\n".getBytes());
    		for (FlowType i: types.values()) {
    			i.Write(out, depth+1);
    		}
    		for (int i=0 ; i<children.length ; i++) {    		
    	    	/* need to deal with splice instances in live graph */
    			if(childalias[i]!=null){
					Node t;
					t = new SpliceNode(childalias[i],children[i].GetID());

    				t.Write(out, depth+1);
    				//Node.DeRegisterID(t.GetID());
    				t = null;
    			}
    			else
    				children[i].Write(out, depth+1);
    		}
    		Indent(out, depth);
    		out.write(("</" + TagName() + ">\n").getBytes());
    	} else {
    		out.write("/>\n".getBytes());
    	}
    }

    /**
     * serialize the node and all descendants to the provided stream,
     * tabbed in depth amount.  Handles resolved splices such that
     * the output should show splice nodes (and nodes should not
     * have multiple parents).
     */
    public void Write(OutputStream out, int depth) throws java.io.IOException
    {
    	WriteBasis(out,depth,null);
    }

    public final static void Indent(OutputStream out, int depth) 
	throws java.io.IOException
    { 
    	int i; for (i=0 ; i<depth ; i++) out.write("\t".getBytes()); 
    }
  
    /**
     * set the URI of the SXE hosting this resource
     * 
     * @param uri
     */
	public void setSXE(java.net.URI uri){
		sxeUri = uri;
	}

    /**
     * get the URI of the SXE hosting this resource
     */
	public java.net.URI getSXE(){
		return sxeUri;
	}
	
	/**
	 * returns a link to the data of this node, via
	 * the SXE that is hosting it
	 * 
	 * @return
	 * @throws URISyntaxException
	 * @throws NullPointerException
	 */
	public String getSDXML() 
	throws URISyntaxException, NullPointerException{
		return "<" + TagName() + " " + 
		"xmlns=\"" + XML.XMLNS + "\" " +
		"id=\"" + ID + "\" href=\"" + getSXELink("data").toString() + "\" />";
	}
	
	/**
	 * returns a the SXE host out to the nodeID of this node (and appends
	 * @param s to the end of the URI)
	 * @return
	 * @throws URISyntaxException
	 * @throws NullPointerException
	 */
	public java.net.URI getSXELink(String s) 
	throws URISyntaxException, NullPointerException {
		/* look up the SXE that owns this node */
		/* get the URI for this SXE, then this node */
		if(sxeUri==null)
			throw new NullPointerException();
		
		return new java.net.URI(sxeUri + "/snbench/sxe/node/" + ID + "/" + s );
		
	}

	/* a sloppy test of whether two nodes are functionally equivalent 
	 * test assumes this node is stronger and the param is to beinserted
	 * such that slack should occur in toBeInserted */
	public boolean functionalEquiv(Node toBeInserted) {
		if(!this.TagName().equals(toBeInserted.TagName()))
			return false;
		if(this.children.length!=toBeInserted.children.length)
			return false;
		for(int i=0;i<children.length;i++){
			if(!this.children[i].functionalEquiv(toBeInserted.children[i]))
					return false;
		}
		if(toBeInserted.bindTo==null)
			return true;
		
		if(toBeInserted.bindTo.equals(this.bindTo))
			return true;

		return false;
	}

	
	/**
	 *  set this.bindTo to be equal to targetNode.bindTo
	 *  and do the same for all children.
	 * 
	 * @param targetNode
	 */
	public void subTreeBindTo(step.Node targetNode){
		this.setBindTo(targetNode.getBindTo());
		this.cost = 0;
		if(!(this instanceof LastTriggerEval))
			for(int i = 0; i < this.children.length ; i++){
				this.children[i].subTreeBindTo(targetNode.children[i]);
			}
	}
	
	public void setBindTo(String strBindTo) {
		bindTo = strBindTo;

	}
	public String getBindTo() {
		if(bindTo!=null)
			return bindTo;
		else
			return "";
	}
	
	public void setBindingSuggested(String strBindTo) {
		bindingSuggested = strBindTo;

	}
	public String getBindingSuggested() {
		return bindingSuggested;
	}

	
	/*****************
	 * Walks this node and all children setting
	 * bindingSuggested to the specified parameter if
	 * existing value is null.
	 * 
	 * returns true if *any* values are changed.
	 */
	public boolean colorWalk(String color){
		boolean bRet = false;
		if(bindingSuggested==null){
			bindingSuggested = color;
			bRet = true;
		}
			
		if(!(this instanceof LastTriggerEval))
			for(int i=0;i<children.length;i++){
				bRet = (bRet || children[i].colorWalk(color));
			}
		return bRet;
	}

	// this code is added by ray//	
	// EFFECT: thsi abstracts function forces each node to perform a validation check, this way we implement type checker
	public abstract void validate(step.Graph g,
			ArrayList<STEPException> compilationErrors);
	
	/**
	 * @param label - label of the FlowType 
	 * @return - a FlowType object or...
	 * 
	 * @throws NoSuchElementException - if the label is not found
	 */
	public FlowType getFlowType(String label) {
		if (types.containsKey(label)) return types.get(label);
		throw new NoSuchElementException("Flowtype label "+label+" not present");
	}

	/**
	 * exceedingly dangerous method.  Use with caution.  Do not modify 
	 * directly as doing so will break links.
	 * @return array of nodes that are this node's parents
	 */
	public Node[] getParents() {
		return parents;
	}
	
	/**
	 * exceedingly dangerous method.  Use with caution.  Do not modify 
	 * directly as doing so will break links.
	 * @return array of nodes that are this node's children
	 */
	public Node[] getChildren() {
		return children;
	}
	
	public String getGraphID() {
		return SourceGraphID;
	}

	public int getCost(){
		return cost;
	}
	
	/**
	 * Returns a HashMap of all of a nodes ancestors in a
	 * cycle safe way (does not go through last trigger evals)
	 * 
	 * this will *not* work is spices are dangling. 
	 * 
	 * @param this - the node from which to start the ascent
	 * @return a Map of all ancestors to this node
	 */
	protected Map<String,Node> GetAllAncestorsCycleSafe(){
		LinkedList<Node> workQueue = new LinkedList<Node>();
		Map<String,Node> upQueue = new HashMap<String,Node>();
		Map<String,String> visited = new HashMap<String,String>();
		
		Node n = this;
		
		workQueue.add(n);
		visited.put(n.GetID(),n.GetID());
		while(!workQueue.isEmpty()){
			Node t = workQueue.remove();
			upQueue.put(t.GetID(),t);
			for(Node p:t.getParents()){
				if(!(p instanceof LastTriggerEval))
					if(!visited.containsKey(p.GetID())){
						visited.put(p.GetID(),p.GetID());
						workQueue.add(p);
					}
			}
		}
		return upQueue;
	}	

	/**
	 * Returns a HashMap of all of a nodes descendants in a
	 * cycle safe way (does not go through last trigger evals)
	 * 
	 * this will *not* work is spices are dangling. 
	 * 
	 * @param this - the node from which to start the ascent
	 * @return a Map of all ancestors to this node
	 */
	protected Map<String,Node> GetAllDescendantsCycleSafe(){
		LinkedList<Node> workQueue = new LinkedList<Node>();
		Map<String,Node> upQueue = new HashMap<String,Node>();
		Map<String,String> visited = new HashMap<String,String>();
		
		Node n = this;
		
		workQueue.add(n);
		visited.put(n.GetID(),n.GetID());
		while(!workQueue.isEmpty()){
			Node t = workQueue.remove();
			upQueue.put(t.GetID(),t);
			if(!(t instanceof LastTriggerEval))
				for(Node p:t.getChildren()){
					if(!visited.containsKey(p.GetID())){
						visited.put(p.GetID(),p.GetID());
						workQueue.add(p);
					}
				}
		}
		return upQueue;
	}	

	public int GetDescendantsCount(){
		return this.GetAllDescendantsCycleSafe().size();
	}
	
    public String toString(){
    	return ID + "/" + getClass().getSimpleName(); 
    }

    /**
     * a method useful for debugging. Shows this node and all ancestors as functional code
     * 
     * @return
     */
    public String serializeAsSnafu(){
    	StringBuffer sb = new StringBuffer(TagName());

    	if(!IsLeaf() && (!(this instanceof LastTriggerEval))){
    		sb.append("(");
    		sb.append(children[0].serializeAsSnafu());
    		for(int i=1;i<children.length;i++){
        		sb.append(",");
        		sb.append(children[i].serializeAsSnafu());
    		}
    		sb.append(")");
    	}
    	return sb.toString();
    }
    
    
    
}

